psychologywikiaorg-20200213-history
Directed acyclic graph
In computer science and mathematics, a directed acyclic graph, also called a DAG, is a with no ; that is, for any vertex v'', there is no nonempty directed path that starts and ends on ''v. DAGs appear in models where it doesn't make sense for a vertex to have a path to itself; for example, if an edge u''→''v indicates that v'' is a part of ''u, such a path would indicate that u'' is a part of itself, which is impossible. Informally speaking, a DAG "flows" in a single direction. Each directed acyclic graph gives rise to a partial order ≤ on its vertices, where ''u ≤ v'' exactly when there exists a directed path from ''u to v'' in the DAG. However, many different DAGs may give rise to this same reachability relation. Among all such DAGs, the one with the fewest edges is the transitive reduction of each of them and the one with the most is their transitive closure. In particular, the transitive closure ''is the reachability order ≤. Terminology A source is a vertex with no incoming edges, while a sink is a vertex with no outgoing edges. A finite DAG has at least one source and at least one sink. The depth of a vertex in a finite DAG is the length of the longest path from a source to that vertex, while its height is the length of the longest path from that vertex to a sink. The length of a finite DAG is the length (number of edges) of a longest directed path. It is equal to the maximum height of all sources and equal to the maximum depth of all sinks. Properties Every directed acyclic graph has a topological sort, an ordering of the vertices such that each vertex comes before all vertices it has edges to. In general, this ordering is not unique. Any two graphs representing the same partial order have the same set of topological sort orders. DAGs can be considered to be a generalization of trees in which certain subtrees can be shared by different parts of the tree. In a tree with many identical subtrees, this can lead to a drastic decrease in space requirements to store the structure. Conversely, a DAG can be expanded to a forest of rooted trees using this simple algorithm: * While there is a vertex v'' with in-degree ''n > 1, ** Make n'' copies of ''v, each with the same outgoing edges but no incoming edges. ** Attach one of the incoming edges of v'' to each vertex. ** Delete ''v. If we explore the graph without modifying it or comparing nodes for equality, this forest will appear identical to the original DAG. Some algorithms become simpler when used on DAGs instead of general graphs. For example, search algorithms like depth-first search without iterative deepening normally must mark vertices they have already visited and not visit them again. If they fail to do this, they may never terminate because they follow a cycle of edges forever. Such cycles do not exist in DAGs. A polytree is a specifically efficient kind of DAG, with many tree-like properties. Its efficiency is exploited, for example, in the belief propagation algorithm for Bayesian networks. The number of Non-Isomorphic DAGs is obtained by Weisstein's conjecture : the number of DAGs on n'' vertices is equal to the number of ''n''x''n matrices with entries from {0,1} and only positive real eigenvalues, proved by McKay et al. McKay, B. D.; Royle, G. F.; Wanless, I. M.; Oggier, F. E.; Sloane, N. J. A.; and Wilf, H. "Acyclic Digraphs and Eigenvalues of (0,1)-Matrices." J. Integer Sequences 7, Article 04.3.3, 1-5, 2004. http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.pdf or http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html. Applications Directed acyclic graphs have many important applications in computer science, including: * Parse trees constructed by compilers * Bayesian networks * Reference graphs that can be garbage collected using simple reference counting * Reference graphs of purely functional data structures (although some languages allow purely functional cyclic structures) * Dependency graphs such as those used in instruction scheduling and makefiles * Dependency graphs between classes formed by inheritance relationships in object-oriented programming languages * Serializability Theory of Transaction Processing Systems * Information categorization systems, such as file system directories * Hierarchical scene graphs to optimise view frustum culling operations * Directed acyclic word graph data structure to memory-efficiently store a set of strings (words) * Forward chained rules systems (including business rules engines) such as the Rete algorithm, used by Drools (a.k.a. JBoss Rules) * Representing spacetime as a causal set in theoretical physics * In bioinformatics, finding areas of synteny between two genomes * Abstract process descriptions such as workflows and some models of provenance * Dynamic Programming References External links * * Category:Graph families